package com.kevinkk.dp;

/**
 * 给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数，结果需要对 109 + 7 取模
 *
 * 1. dp[i][j]：以i-1为结尾的s子序列中出现以j-1为结尾的t的个数
 * 2. dp公式
 *      if (sChar[i - 1] == tChar[j - 1]) {
 *          dp[i][j] = dp[i - 1][j - 1] + dp[i-1][j];   ---> 还可以删除 s 中的一个元素
 *      } else {
 *          dp[i][j] = dp[i-1][j];                      ---> 删除 s 中的一个元素
 *      }
 * 3. 初始化
 *      之前的子序列中，dp 数组的含义一般都是以 text1[i-1]和 text2[j-1] 结尾的最长子数组的长度，因此不需要进行初始化操作
 *      而这一题 dp 数组的含义是个数，因此需要进行初始化
 *      dp[i][0] 表示 数组 s 中空字符串的个数，那么就是 i
 *      dp[0][j] 表示 空字符串中有多少个字符串 t，那么都是 0
 * 4. 遍历顺序
 */

public class DistinctSubsequences {
    class Solution {
        public int numDistinct(String s, String t) {
            char[] sChar = s.toCharArray(), tChar = t.toCharArray();
            int[][] dp = new int[sChar.length + 1][tChar.length + 1];
            for(int i  = 0; i <= sChar.length; i++)
                dp[i][0] = 1;

            for (int i = 1; i <= sChar.length; i++) {
                for (int j = 1; j <= tChar.length; j++) {
                    if (sChar[i - 1] == tChar[j - 1]) {
                        dp[i][j] = dp[i - 1][j - 1] + dp[i-1][j];
                    } else {
                        dp[i][j] = dp[i-1][j];
                    }
                }
            }

            return dp[sChar.length][tChar.length];

        }
    }
}
